
/**
 * A class that represents a value to be sorted by the <tt>BiSort</tt>
 * algorithm.  We represents a values as a node in a binary tree.
 **/
class Value
{
    private int value;
    private Value left;
    private Value right;

    static final boolean FORWARD = false;
    static final boolean BACKWARD = true;

    // These are used by the Olden benchmark random no. generator
    private static final int CONST_m1 = 10000;
    private static final int CONST_b = 31415821;
    static final int RANGE = 100;

    /**
     * Constructor for a node representing a value in the bitonic sort tree.
     * @param v the integer value which is the sort key
     **/
    Value(int v)
    {
        value = v;
        left = right = null;
    }

    /**
     * Create a random tree of value to be sorted using the bitonic sorting algorithm.
     *
     * @param size the number of values to create.
     * @param seed a random number generator seed value
     * @return the root of the (sub) tree.
     **/
    static Value createTree(int size, int seed)
    {
        if (size > 1) {
            seed = random(seed);
            int next_val = seed % RANGE;

            Value retval = new Value(next_val);
            retval.left = createTree(size/2, seed);
            retval.right = createTree(size/2, skiprand(seed, size+1));
            return retval;
        } else {
            return null;
        }
    }

    /**
     * Perform a bitonic sort based upon the Bilardi and Nicolau algorithm.
     *
     * @param spr_val the "spare" value in the algorithm.
     * @param direction the direction of the sort (forward or backward)
     * @return the new "spare" value.
     **/
    int bisort(int spr_val, boolean direction)
    {
        if (left == null) {
            if ((value > spr_val) ^ direction) {
                int tmpval = spr_val;
                spr_val = value;
                value = tmpval;
            }
        } else {
            int val = value;
            value = left.bisort(val, direction);
            boolean ndir = !direction;
            spr_val = right.bisort(spr_val, ndir);
            spr_val = bimerge(spr_val, direction);
        }
        return spr_val;
    }

    /**
     * Perform the merge part of the bitonic sort.  The merge part does
     * the actualy sorting.
     * @param spr_val the "spare" value in the algorithm.
     * @param direction the direction of the sort (forward or backward)
     * @return the new "spare" value
     **/
    int bimerge(int spr_val, boolean direction)
    {
        int   rv = value;
        Value pl = left;
        Value pr = right;

        boolean rightexchange = (rv > spr_val) ^ direction;
        if (rightexchange) {
            value = spr_val;
            spr_val = rv;
        }

        while (pl != null) {
            int   lv  = pl.value;
            Value pll = pl.left;
            Value plr = pl.right;
            rv        = pr.value;
            Value prl = pr.left;
            Value prr = pr.right;

            boolean elementexchange = (lv > rv) ^ direction;
            if (rightexchange) {
                if (elementexchange) {
                    pl.swapValRight(pr);
                    pl = pll;
                    pr = prl;
                } else {
                    pl = plr;
                    pr = prr;
                }
            } else {
                if (elementexchange) {
                    pl.swapValLeft(pr);
                    pl = plr;
                    pr = prr;
                } else {
                    pl = pll;
                    pr = prl;
                }
            }
        }

        if (left != null) {
            value = left.bimerge(value, direction);
            spr_val = right.bimerge(spr_val, direction);
        }
        return spr_val;
    }

    /**
     * Swap the values and the right subtrees.
     * @param n the other subtree involved in the swap.
     **/
    void swapValRight(Value n)
    {
        int   tmpv = n.value;
        Value tmpr = n.right;

        n.value = value;
        n.right = right;

        value = tmpv;
        right = tmpr;
    }

    /**
     * Swap the values and the left subtrees.
     * @param n the other subtree involved in the swap.
     **/
    void swapValLeft(Value n)
    {
        int   tmpv = n.value;
        Value tmpl = n.left;

        n.value = value;
        n.left  = left;

        value = tmpv;
        left  = tmpl;
    }

    /**
     * Print out the nodes in the binary tree in infix order.
     **/
    void inOrder()
    {
        if (left != null)
            left.inOrder();
        System.out.println(value + " " + hashCode());
        if (right != null)
            right.inOrder();
    }


    /**
     * A random generator.  The original Olden benchmark uses its
     * own random generator.  We use the same one in the Java version.
     * @return the next random number in the sequence.
     **/
    private static int mult(int p, int q)
    {
        int p1 = p/CONST_m1;
        int p0 = p%CONST_m1;
        int q1 = q/CONST_m1;
        int q0 = q%CONST_m1;
        return (((p0*q1+p1*q0) % CONST_m1) * CONST_m1+p0*q0);
    }

    /**
     * A routine to skip the next <i>n</i> random numbers.
     * @param seed the current random no. seed
     * @param n the number of numbers to skip
     **/
    private static int skiprand(int seed, int n)
    {
        for (; n != 0; n--) seed = random(seed);
        return seed;
    }

    /**
     * Return a random number based upon the seed value.
     * @param seed the random number seed value
     * @return a random number based upon the seed value.
     **/
    static int random(int seed)
    {
        int tmp = mult(seed, CONST_b) + 1;
        return tmp;
    }
}

